#define _CRT_SECURE_NO_WARNINGS

#include "tree.h"
#include <stdlib.h>
#include <string.h>

#define MAXNUMVALUES 100
#define NOT_IN_USE -1

static char stringValues[MAXNUMVALUES * 3]; //Temporary storage of user input of nodevalues as a string
static int nodeValues[MAXNUMVALUES]; //Temporary storage of user input of nodevalues as numbers.
static int numValues = 0; //number of values the user input, count of nodeValues.




typedef struct cellT{
	int node[2];
	struct cellT *rev;
	struct cellT *child_1;
	struct cellT *child_2;
	struct cellT *child_3;
}cellT;

typedef struct treeCDT {
	cellT *tree;
} treeCDT;

cellT nodes[7];

static void printTreeC(cellT *tree);
static void populateTree();
static void askUserElements(void);
cellT* newCellT(void);
void sortNode(cellT *cell);
static cellT *insertRight(cellT *cell, int value);
static int middleIndex(cellT *cell, int value);
static void traverse(cellT *cell, int value);
static void traverseLeft(cellT *cell, int value);
static int isLeaf(cellT *cell);
static int isThreeNode(cellT cell);
static int middleIndex(cellT *cell, int value);
static int lowIndex(cellT *cell, int value);
static int highIndex(cellT *cell, int value);

static int isThreeNode(cellT cell){
	int i;

	for (i = 0; i < 2; i++){
		if (cell.node[i] == NOT_IN_USE)
			return FALSE;
	}

	return TRUE;
}

void init(){
	internalTree = (treeADT)malloc(sizeof(treeCDT));
	internalTree->tree = NULL;
	//populateTree();
}


treeADT insertElement(){
	askUserElements();


	traverse(internalTree->tree, 5);
	internalTree->tree = insertRight(internalTree->tree, 5);
	traverse(internalTree->tree, 10);
	internalTree->tree = insertRight(internalTree->tree, 10);
	traverse(internalTree->tree, 40);
	internalTree->tree = insertRight(internalTree->tree, 40);
	traverse(internalTree->tree, 20);
	internalTree->tree = insertRight(internalTree->tree, 20);
	traverse(internalTree->tree, 60);
	internalTree->tree = insertRight(internalTree->tree, 60);

	return internalTree;
}

void sortNode(cellT *cell){
	int temp;
	if (cell->node[0] > cell->node[1]){
		temp = cell->node[1];
		cell->node[1] = cell->node[0];
		cell->node[0] = temp;
	}
}

static int isLeaf(cellT *cell){
	if (cell == NULL)
		return TRUE;
	return (cell->child_1 == NULL);
}

static void traverse(cellT *cell, int value){
	if (isLeaf(cell)){
		return;
	}

	else if (isThreeNode(*cell)){
		if (value < cell->node[0])
			traverse(cell->child_1, value);
		else if (value > cell->node[0] && value < cell->node[1])
			traverse(cell->child_2, value);
		else
			traverse(cell->child_3, value);
	}
	else{
		if (value < cell->node[0])
			traverse(cell->child_1, value);
		else
			traverse(cell->child_2, value);
	}
}

static int middleValue(cellT cell, int value){
	if (value > cell.node[0] && value < cell.node[1]){
		return value;
	}
	else if (value > cell.node[1]){
		return cell.node[1];
	}

	return cell.node[0];
}

static int lowValue(cellT cell, int value){
	if (value < cell.node[0] && value < cell.node[1]){
		return value;
	}

	return cell.node[0];
}

static int highValue(cellT cell, int value){
	if (value > cell.node[1]){
		return value;
	}

	return cell.node[1];
}

static int middleIndex(cellT *cell, int value){
	if (value > cell->node[0] && value < cell->node[1]){
		return (-1);
	}
	else if (value > cell->node[1]){
		return 1;
	}

	return 0;
}

static int lowIndex(cellT *cell, int value){
	if (value < cell->node[0]){
		return -1;
	}

	return 0;
}

static int highIndex(cellT *cell, int value){
	if (value > cell->node[1]){
		return -1;
	}

	return cell->node[1];
}

static int isTreeEmpty(void){
	return (internalTree == NULL);
}

static int topValue(cellT *cell){
	if (cell->rev == NULL){
		return cell->node[0];
	}

	return topValue(cell->rev);
}

static cellT *insertRight(cellT *cell, int value){
	int midIndex, lIndex;

	if (cell == NULL){
		cellT *newValue;
		newValue = newCellT();
		cell = newValue;
		cell->node[0] = value;
		cell->node[1] = NOT_IN_USE;
	}
	else if (cell->node[1] == NOT_IN_USE){
		cell->node[1] = value;
		sortNode(cell);
	}
	else if (isThreeNode(*cell)){
		if (cell->rev == NULL){
			cell->rev = insertRight(cell->rev, middleValue(*cell, value));
			if (midIndex = middleIndex(cell, value) != NOT_IN_USE){
				cell->node[midIndex] = NOT_IN_USE;
			}
			if (topValue(cell) < value){
				cell->rev->child_1 = insertRight(cell->rev->child_1, lowValue(*cell, value));
				cell->rev->child_1->rev = cell->rev;
				if (lIndex = lowIndex(cell, value) != NOT_IN_USE){
					cell->node[lIndex] = NOT_IN_USE;
				}
				cell->rev->child_3 = cell;
				cell->node[0] = highValue(*cell, value);
				cell->node[1] = NOT_IN_USE;
				if (cell->child_2 != NULL){
					cell->rev->child_1->child_3 = cell->child_2;
				}
			}
			else{
				/* TODO: Handle left insertions */
			}
		}
		else{
			if (topValue(cell) > value){
				insertRight(cell->rev, middleValue(*cell, value));
				if (midIndex = middleIndex(cell, value) != NOT_IN_USE){
					cell->node[midIndex] = NOT_IN_USE;
				}
				cell->node[0] = lowValue(*cell, value);
				cell->node[1] = highValue(*cell, value);
				if (!isThreeNode(*cell->rev)){
					cell->rev->child_2 = insertRight(cell->rev->child_2, lowValue(*cell, value));
				}
			}
			else{
				/* TODO: Handle left insertions */
			}
		}
	}
	return (cell);
	//tree->tree->node[index] = value
}

cellT* newCellT(void){
	cellT *x;
	int i;
	x = (cellT*)malloc(sizeof(cellT));
	for (i = 0; i < 2; i++){
		x->node[i] = 0;
	}
	x->child_1 = NULL;
	x->child_2 = NULL;
	x->child_3 = NULL;
	x->rev = NULL;
	return (x);
}

static void askUserElements(void){
	char *token;
	char *nextToken = NULL;
	int i;
	int node = 0;
	stringValues[0] = '\0';

	numValues = 0;

	printf("\nMaximum %d elements can be inserted at once.\n"
		"Enter an element or elements delimited by spaces: \n", MAXNUMVALUES);

	scanf("%[0-9 -]s", stringValues); // MAXNUMVALUES, stdin);

	fflush(stdin);

	token = strtok_s(stringValues, " ", &nextToken);


	for (i = 0; token != NULL && i < MAXNUMVALUES; i++){
		node = atoi(token);
		nodeValues[numValues++] = node;

		//printf("%d\n", nodeValues[i]);

		token = strtok_s(NULL, " ", &nextToken);
	}

	//Sleep(2000);
}

treeADT newTree(){
	treeADT tree;
	tree = (treeADT)malloc(sizeof(treeCDT));
	tree->tree = NULL;
	return (tree);
}


void deleteElement(treeADT tree){


}

void deleteTree(treeADT tree){


}

void printTree(treeADT tree){

	printTreeC(tree->tree);

}

static void printTreeC(cellT *tree){

	if (tree->child_1 == NULL
		&& tree->child_2 == NULL
		&& tree->child_3 == NULL){
		printf("(%d,%d)", tree->node[0], tree->node[1]);
		return;
	}

	//printf("(Node23 (%d,%d) (%d,%d) (%d,%d) (%d,%d))");
	printf("(Node23 (%d,%d) ", tree->node[0], tree->node[1]);

	if (tree->child_1 != NULL)
		printTreeC(tree->child_1);
	else
		printf("(NIL)");

	printf(" ");

	if (tree->child_2 != NULL)
		printTreeC(tree->child_2);
	else
		printf("(NIL)");

	printf(" ");

	if (tree->child_3 != NULL)
		printTreeC(tree->child_3);
	else
		printf("(NIL)");

	printf(")");

}

static void populateTree(){

	internalTree->tree = &nodes[0];

	internalTree->tree->node[0] = 32;
	internalTree->tree->node[1] = 86;

	internalTree->tree->child_1 = &nodes[1];
	internalTree->tree->child_2 = &nodes[2];
	internalTree->tree->child_3 = &nodes[3];

	internalTree->tree->child_1->node[0] = 15;
	internalTree->tree->child_1->node[1] = 25;
	internalTree->tree->child_2->node[0] = 45;
	internalTree->tree->child_2->node[1] = 55;
	internalTree->tree->child_3->node[0] = 95;
	internalTree->tree->child_3->node[1] = 104;

	internalTree->tree->child_3->child_1 = NULL;
	internalTree->tree->child_3->child_2 = NULL;
	internalTree->tree->child_3->child_3 = NULL;

	internalTree->tree->child_2->child_3 = NULL;
	internalTree->tree->child_2->child_2 = NULL;
	internalTree->tree->child_2->child_1 = NULL;

	internalTree->tree->child_1->child_3 = &nodes[4];
	internalTree->tree->child_1->child_2 = &nodes[5];
	internalTree->tree->child_1->child_1 = &nodes[6];

	internalTree->tree->child_1->child_3->node[0] = 10;
	internalTree->tree->child_1->child_3->node[1] = 14;

	internalTree->tree->child_1->child_2->node[0] = 16;
	internalTree->tree->child_1->child_2->node[1] = 17;

	internalTree->tree->child_1->child_1->node[0] = 28;
	internalTree->tree->child_1->child_1->node[1] = 32;

	internalTree->tree->child_1->child_3->child_1 = NULL;
	internalTree->tree->child_1->child_3->child_2 = NULL;
	internalTree->tree->child_1->child_3->child_3 = NULL;

	internalTree->tree->child_1->child_2->child_1 = NULL;
	internalTree->tree->child_1->child_2->child_2 = NULL;
	internalTree->tree->child_1->child_2->child_3 = NULL;

	internalTree->tree->child_1->child_1->child_1 = NULL;
	internalTree->tree->child_1->child_1->child_2 = NULL;
	internalTree->tree->child_1->child_1->child_3 = NULL;
}